package algorithm.sort;

import java.util.Arrays;

//快速排序
public class QuickSort {

    public static void main(String[] args) {
        int[] data = new int[]{5, 3, -1, 6, 9, 7, 5};
        quickSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }


    public static void quickSort(int[] data, int left, int right) {
        //序列内至少存在2个元素的情况
        if (left < right) {
            int i = partition(data, left, right);
            quickSort(data, left, i - 1);
            quickSort(data, i + 1, right);
        }

    }

    private static int partition(int[] data, int left, int right) {
        int i = left;
        int j = right;
        int pivot = data[left];
        while (i != j) {
            while (j > i && data[j] >= pivot) {
                j--;
            }
            if (j > i) {
                data[i] = data[j];
            }
            while (j > i && data[i] < pivot) {
                i++;
            }
            if (j > i) {
                data[j] = data[i];
            }
        }
        data[i] = pivot;
        return i;
    }


}
